1. Field of the Invention
The present invention relates in general to the field of software testing, and more particularly, to an improved method, system, and computer program product for generating tests for non-deterministic software.
2. Description of the Related Art
As the use of computers has increased over the past several decades, software development has become an important, and quite lucrative, industry. A critical element to successfully bringing software to the marketplace is the ability to quickly and thoroughly test the software while minimizing the impact on the development schedule.
To speed up the process of generating test suites, more recently software testers have turned to automated test generators (e.g. Object Geode by Telelogic) which utilize “behavioral models” and coverage criteria to automatically generate the test suites. The behavioral model is a formal description of part of the behavior of the software under test, and this behavioral model can be utilized by an automated test generator to generate a test suite according to separately defined coverage criteria. Coverage criteria typically comprise an informal list of tasks to be accomplished by the test suite. This may be a subset of states, transitions, or paths within the software under test that need to be covered by the test suite.
In a typical use of an automated test generator, a test engineer writes behavioral models in a formal modeling language that is “understood” by the automated test generator being used. For example, test engineers may use finite state machines to model externally observable behavior of a program under test. They then input the models and coverage criteria to an automated test generator to generate test cases that are combined to form the test suite. There are many well-known methods of this type as disclosed in commonly assigned co-pending U.S. patent application Ser. No. 09/847,309 entitled “Technique Using Persistent Foci for Finite State Machine-Based Test Generation,” filed on May 31, 2001, incorporated herein fully by reference.
Non-determinisitic software is software that is implemented such that multiple outputs (referred to herein as “outcome states”) may occur for the same input sequence (referred to herein as a “stimulus”) and system state (referred to herein as a “current state”). While this is extremely important to the growth in software development and to the implementation of distributed processing, non-deterministic software creates significant challenges for those who test the software, in that a given stimulus and current state cannot guarantee a unique output state. One form of non-determinism common in software development today involves non-determinism of the software itself where there can be multiple correct output states for a single set of stimuli.
A simplistic example of this form of non-determinism can be found in file systems and the mechanism by which access is allowed to files. In a network environment, for example, multiple users of a word processing program may have access to text files stored in a common network drive. When a user “A” wishes to access a particular file (e.g., “Hartman.doc”) from a “current state” (e.g., while viewing a list of file names in a word processing program), user A “double clicks” on “Hartman.doc” from the file list, resulting in the opening of the file “Hartman.doc” into the word processing program for editing. The act of “double clicking” is a stimulus applied to a current state (the display of the file list) which causes a valid outcome state, i.e., the opening of the file.
However, suppose two users “A” and “B” simultaneously attempt to access this file for purposes of editing. If users A and B are simultaneously allowed access to “Hartman.doc” and each edits the file, two different “originals” of the same document will be created, and when they are saved, one will overwrite the other. To avoid this occurrence, many file systems are designed to allow access to a particular file by more than one user, but only one user at a time may alter a file's contents. Thus, the result occurring from a single stimulus, e.g., double clicking on the file “Hartman.doc,” is two (or more) different but valid outcome states. One valid outcome state is that user A is given writing access to the file to the exclusion of all others, and the second valid outcome state is that user B is given writing access to the file to the exclusion of all others.
For purposes of testing, this presents a dilemma. In the scenario described above, applying a single stimulus to software in a current state will have more than one correct outcome state. Thus, if the test is performed and a “pass” response is received, all that is known is that one of the correct paths passed the test, and nothing is known about the alternative path(s).
Prior art attempts have been made to overcome this problem. There are three main approaches to the testing of non-deterministic software:
Non-deterministic testing: Each test case is run many times and the actual outcomes are observed each time. This mode of testing suffers from three main problems: First, certain outcomes may be repeated many times, which is inefficient use of testing resources. Second, some outcomes which are valid may never be observed, due to their having a low probability of occurrence. Third, and most serious, is that it is impossible to detect with certainty a defect in the program which actually does not implement all the possible outcomes.
Deterministic testing: In order to force the program to exercise all possible outcomes, code is added to the program, or to the operating system, which gives the tester more control over the outcomes of a stimulus. This method of testing is preferable, but in many cases it is impossible since the tester does not have access to the source code of the program under test.
Interleaving test generation and execution: In this method the stimuli to be applied to the program are not predetermined, but chosen in response to the observed outcome of prior stimuli. This interleaving requires the use of scarce computing resources for both the tasks of test execution and next stimulus selection concurrently. Often this is not feasible due to the time sensitivity of the program under test, and it may also change the behavior of the program due to the increased delays between stimuli. Furthermore, it also suffers from the same problems as non-deterministic testing in that it is impossible to detect with certainty a defect in the program that actually does not implement all the possible outcomes. See Carver and Tai, “Use of sequencing constraints for specification-based testing of concurrent program,” IEEE Transactions of SW Engineering, Vol. 24, No. 6, pp. 471–490 (June 1998).
Accordingly, it would be desirable to have the ability to model more than one behavior based upon a single stimulus, thereby allowing for automated test generation for non-determinisitic software.